13
Subsecuencia de suma máxima
Dividiendo el problema
Ejemplo:
Suma máxima incluyendo último primera mitad: 4
Idem primer elemento segunda mitad: 7
Total: 11 (mayor que máximo en ambas mitades)
14
Subsecuencia de suma máxima
Algoritmo:
Dividir secuencia en dos (izquierda, derecha)
Resolver recursivamente las mitades
Caso base: secuencia de largo 1
Calcular suma máxima centro (borde izquierdo + borde derecho)
Retornar max{izquierda, derecha, centro}
15
Subsecuencia de suma máxima
Complejidad del algoritmo:
Dos llamadas recursivas de tamaño n/2
Suma máxima centro: O(n)
Ecuación de recurrencia:
16
Subsecuencia de suma máxima
Tiempo: O(n log(n))
Solución 4: Algoritmo eficiente
Observaciones:
No es necesario conocer donde esta la mejor subsecuencia
La mejor subsecuencia no puede comenzar en un número negativo
Cualquier subsecuencia negativa no puede ser prefijo de la subsecuencia óptima
17
Subsecuencia de suma máxima
Solución 4: Algoritmo eficiente
Inducción (reforzada)
Se conoce la mejor subsecuencia entre 1 y j
Se conoce la mejor subsecuencia que termina en j
Algoritmo
Se almacenan ambos valores (inicialmente 0)
Se incrementa j en 1
Se actualiza mejor subsecuencia si es necesario
Si subsecuencia que termina en j es < 0 se puede descartar, volver su valor a 0
18
Subsecuencia de suma máxima
Seudocódigo
int maxSum = 0, thisSum = 0;
for( j=0; j< a.length; j++)
{
thisSum += a[j];
if (thisSum > maxSum)
maxSum = thisSum;
else if (thisSum < 0)
thisSum = 0;
}
19
Subsecuencia de suma máxima
Tiempo de la solución eficiente: O(n)
20
Multiplicación de matrices
Problema numérico fundamental
A, B matrices de N x N
Se desea calcular C = A * B
21
Multiplicación de matrices
Algoritmo simple:
// A, B: matrices de N x N
int[][] C=new int[N][N];
for( int i=0; i< n; i++) // Inicializacion
for (int j=0; j< n; j++)
C[i][j]=0;
for( int i=0; i< n; i++)
for (int j=0; j< n; j++)
for (int k=0; k< n; k++)
C[i][j]+=A[i][k]*B[k][j];
22
Multiplicación de matrices
Tiempo algoritmo simple: O(N3)
Por largo tiempo se supuso cota W(N3)
En los 60', Strassen mostró como romper la barrera W(N3)
Idea del algoritmo de Strassen:
Dividir cada matriz en cuatro cuadrantes
23
Multiplicación de matrices
Descomposición de AB=C en cuatro cuadrantes
24
Multiplicación de matrices
Se realizan 8 multiplicaciones de matrices de N/2 x N/2
25
Multiplicación de matrices
Tiempo: O(N3)
Mejora: disminuir número de subproblemas
Estrategia de Strassen:
26
Multiplicación de matrices
Respuesta final:
27
Multiplicación de matrices
Complejidad ahora satisface la recurrencia
28
Multiplicación de matrices
Detalles a considerar:
N no es potencia de 2 (detalle menor)
En la práctica, algoritmo de Strassen funciona mejor que el algoritmo simple cuando N es "grande"
Numéricamente inestable
Sin embargo, representa un resultado interesante desde el punto de vista teórico
29
Subsecuencia común más larga
Problema: comparar dos secuencias de ADN
ADN: secuencia de moléculas llamadas bases
Se puede representar como un string (A, C, G, T)
Cómo determinar si dos secuencias son similares
Una es substring de la otra
Costo de transformar una en otra (distancia edición)
Encontrar una tercera que se parezca a ambas
30
Subsecuencia común más larga
Definiciones
Subsecuencia: la secuencia con cero o más elementos dejados fuera
Formalmente:
Z es subsecuencia de X si existe secuencia de índices creciente de X tal que
31
Subsecuencia común más larga
Definiciones
Z es subsecuencia común de X e Y si es subsecuencia de X y de Y
Ejemplos:
Problema: encontrar subsecuencia común más larga (LCS) de X e Y
32
Subsecuencia común más larga
Solución por fuerza bruta:
Enumerar todas las subsecuencias de X
Chequear cada una si es también subsecuencia de Y
Guardar la subsecuencia común más larga
X tiene 2m subsecuencias
Tiempo: O(2m)
33
Subsecuencia común más larga
Idea: intentar dividir el problema
Definición: i-ésimo prefijo de X
Subproblemas de LCS: prefijos de X e Y
34
Subsecuencia común más larga
Teorema: Subestructura óptima de una LCS
X (m) e Y (n) secuencias, Z (k) una LCS de X e Y
35
Subsecuencia común más larga
Teorema implica revisar uno o dos subproblemas
La solución del subproblema es parte de la solución final (óptima)
Nota: Encontrar LCS de casos (2) y (3) del Teorema implica calcular LCS de Xm-1 e Yn-1
Muchos subproblemas comparten otros subproblemas
Total subproblemas distintos: m*n
36
Subsecuencia común más larga
Solución: Programación dinámica
Definición: Matriz C de m x n
Algoritmo: llenar tabla en forma bottom-up
37
Subsecuencia común más larga
Implementación:
m=X.length-1; n=Y.length-1; // indices 1 a m,n
for(i=1; i< =m; i++) c[i,0]=0;
for(j=0; j< =n; j++) c[0,j]=0;
for(i=1; i< =m; i++)
for(j=1; j< =n; j++)
if (X[i]==Y[j]){
c[i,j]=c[i-1,j-1]+1; b[i,j]="";}
else if (c[i-1,j]>=c[i,j-1]){
c[i,j]=c[i-1,j]; b[i,j]=""}
else{
c[i,j]=c[i-1,j]; b[i,j]="-"}
return {c,b};
38
Subsecuencia común más larga
Ejemplo:
Para imprimir LCS
void LCS(b,X,i,j){
if (i==0 || j==0)
return;
if (b[i,j]==""){
LCS(b,X,i-1,j-1);
print(X[i]);}
else if (b[i,j]=="")
LCS(b,X,i-1,j);
else \ "-"
LCS(b,X,i,j-1);
}
39
Selección del k-ésimo
Selección (k-ésimo)
Problema: dado un arreglo desordenado encontrar el k-ésimo del conjunto
Determinar mínimo o máximo: O(n) (cota mínima)
Supongamos una especie de torneo entre elementos, x es el primero (máximo)
El segundo puede ser cualquiera de los que perdieron directamente con x
40
Selección del k-ésimo
Luego, para calcular segundo, tercero, ., toman tiempo:
Segundo: n+log2n
Tercero: n+2log2n
.
k: n+(k-1)log2n
Esto está bien para k constante, pero para un k genérico (como la mediana)
k=n/2: O(n log n)
41
Selección del k-ésimo
Quickselect
Se basa en el tipo de operaciones de quicksort
Se escoge pivote al azar
Se particiona el arreglo de acuerdo al pivote escogido
Si el pivote cae más allá de la posición k, sólo se ordena la parte izquierda
Si el pivote estaba en la posición k, lo encontramos de inmediato
42
Selección del k-ésimo
Seudocódigo
Quickselect(S,k)
{
Sea p en S
S1 = {x en S, x < p}
S2 = {x en S, x > p}
Si k < = |S1| return Quickselect(S1,k)
Si k = |S1|+1 return p
return Quickselect(S2, k-|S1|-1)
}
43
Selección del k-ésimo
Peor caso: O(n2) (mala elección del pivote)
Caso promedio: O(n)
En la práctica este algoritmo es muy rápido, pero su peor caso es pésimo
Uno quisiera asegurar una garantía de orden lineal para encontrar el k-ésimo
Idea: buscar un pivote tal que deje fuera por lo menos una fracción fija del total de elementos
44
Selección del k-ésimo
Método de selección lineal
Dividir S en |S/5| conjuntos (cada Si contiene 5 elementos)
Obtener las medianas m1, m2, .
Obtener p=Select({mi}, (|S|/5)/2) (mediana de las medianas)
45
Selección del k-ésimo
Características de p
Mayor que la mitad de las medianas
Menor que la otra mitad de las medianas
De los grupos con medianas menores (que fueron obtenidas de entre 5 elementos)
3 elementos son menores que p
De los grupos con medianas mayores
3 elementos son mayores que p
Esto implica que 3/10 elementos son menores que p y que 3/10 son mayores que p
46
Selección del k-ésimo
El pivote p sólo puede ser mayor que el 3/10 menor y menor que el 3/10 mayor de S
En el peor caso habrá que buscar recursivamente en un grupo con 7/10 de los elementos
Cálculo de mi y particiones + cálculo de mediana de medianas + recursión sobre (7/10)n restantes
47
Selección del k-ésimo
Suponiendo solución O(n)
48
Selección del k-ésimo
La elección de 5 elementos para los grupos Si se debe a que:
Este número debe ser impar para obtener mediana exacta
Debe ser mayor o igual a 5 para asegurar linealidad del algoritmo
Se escoge 5 porque:
Mediana de medianas queda muy a la mitad
Para números muy grandes de elementos calcular las medianas toma tiempo mayor
 Página anterior | Volver al principio del trabajo | Página siguiente  |